package com.baidu.leetcode.search;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * @author shilei
 * @create 2021-12-10 14:06
 * 二分查找算法演示 必须是数组有序
 * 二分查找思路分析：
 * 1、首先确定该数组的中间的下标 mid=(left+right)/2
 * 2.1、findVal > arr[mid] 说明你要查找的数在 mid 右边 因此需要递归向右查找
 * 2.2、findVal < arr[mid] 说明你要查找的数在mid 的左边 因此需要递归的向左查找
 * 3.3、findVal = arr[mid] 说明找到 返回
 * <p>
 * 考虑什么时候需要结束递归
 * 1、找到就结束递归
 * 2、递归完整个数组、仍然没有找到 findVal 也需要结束递归 当 left > right 就需要退出
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
        int i = binarySearch(arr, 0, arr.length - 1, 10000);
        System.out.println(i);
        List<Integer> list = binarySearchList(arr, 0, arr.length - 1, 1000);
        System.out.println(list);
    }

    /**
     * 二分查找演示-前提数组必须是有序
     *
     * @param arr     原始数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找当前数
     * @return 如果找到就返回下标 如果找不到就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //当 left > right 就说明没有找到当前数 则直接结束递归 否则会栈溢出
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {
            //向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            //向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    //查找所有符合条件的数据的下标索引返回
    public static List<Integer> binarySearchList(int[] arr, int left, int right, int findVal) {
        //当 left > right 就说明没有找到当前数 则直接结束递归 否则会栈溢出
        if (left > right) {
            return Lists.newArrayList();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {
            //向右递归
            return (binarySearchList(arr, mid + 1, right, findVal));
        } else if (findVal < midVal) {
            //向左递归
            return (binarySearchList(arr, left, mid - 1, findVal));
        } else {
            /*
                思路分析：
                    1、在找到mid索引值 不要马上返回
                    2、向mid 索引值的左边扫描 将所有满足条件的数元素的下标 加入到集合中
                    3、想mid 索引值右边扫描 将所有满足条件的数元素的下标 加入到集合中
                    4、将集合返回
             */
            List<Integer> list = Lists.newArrayList();
            //向mid索引值左边扫描 将所有满足条件的元素下标 加入集合
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {//退出
                    break;
                }
                list.add(temp);
                temp -= 1;//temp 左移
            }
            list.add(mid);
            //向mid索引值右边扫描 将所有满足条件的元素下标 加入集合
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
                    break;
                }
                list.add(temp);
                temp += 1;//temp 右移
            }
            return list;
        }
    }
}
